/*
 * Copyright 2012 Alain Pannetrat (L1L1@gmx.com)
 * 
 * This file is part of cookie-miner.
 * 
 * cookie-miner is free software: you can redistribute it and/or modify 
 * it under the terms of the GNU General Public License as published by 
 * the Free Software Foundation, either version 3 of the License, or 
 * (at your option) any later version.
 * 
 * cookie-miner is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License 
 * along with cookie-miner. If not, see http://www.gnu.org/licenses/.
 *
 * @version: $Id$
 *
 */
#include "quadtree.h"
#include <string.h>
#include <stdio.h>
//#include <assert.h>

#define QNODE_ALLOC 1024   // number of qnodes allocated at once
QNode *qnode_free = NULL;  // pointer to first element in free list

void *QNode::operator new(size_t sz)
{
	// * This custom new() allocates qnodes in large blocks 
	//   and recycles qnodes that are released by delete.
	// * qnode_free points to the free list of qnodes. 
	// * Care is taken to zero out qnodes.

	QNode* ret;

	if (qnode_free==NULL)
	{
		ret = (QNode *)new char[QNODE_ALLOC*sz];
		
		memset(ret,0,QNODE_ALLOC*sz);
		
		for (unsigned i=QNODE_ALLOC;i>0;i--)
		{
			ret[i-1]._next_free = qnode_free;
			qnode_free = &(ret[i-1]);
		}
	}
	else
		ret = qnode_free;

	qnode_free = qnode_free->_next_free;
	return ret;
}

void QNode::operator delete(void *nd)
{
	// complement to the custom new() function

	memset(nd,0,sizeof(QNode));
	((QNode *)nd)->_next_free = qnode_free;
	qnode_free = (QNode *)nd;
	//fprintf(stderr,"%p delete()\n",qnode_free);
}

void QNode::force_add(Vertex* v)
{
	// add a vertex a one of the possible 4 children of the qnode.

	float nx = v->position()[0];
	float ny = v->position()[1];
	float vcenter = (_bottom+_top)/2;
	float hcenter = (_right+_left)/2;

	if (nx<hcenter) // are we in the left or right half?
	{
		if (ny<vcenter) // are we in the top or bottom half?
		{
			if (!_tl) _tl = new QNode(_left,_top,hcenter,vcenter);
			_tl->add(v);
		}
		else
		{
			if (!_bl) _bl = new QNode(_left,vcenter,hcenter,_bottom);
			_bl->add(v);
		}
	}
	else
	{
		if (ny<vcenter)
		{
			if (!_tr) _tr = new QNode(hcenter,_top,_right,vcenter);
			_tr->add(v);
		}
		else
		{
			if (!_br) _br = new QNode(hcenter,vcenter,_right,_bottom);
			_br->add(v);
		}
	}
}

void QNode::add(Vertex* v)
{
	float nx = v->position()[0];
	float ny = v->position()[1];

	//fprintf(stderr,"%p adding (%g,%g) in (%g,%g,%g,%g)-%f\n",this,nx,ny,_left,_top,_right,_bottom,_weight);
	if (_weight==0)
	{
		_position[0]=nx;
		_position[1]=ny;
		_weight = 1.0;
		_vertex = v;
		return;
	}

	if (_vertex)	
	{
		// If _vetex is not NULL than this is a leaf node.
		// In the normal case, we will split it in two and
		// create two leaf node from this one, adding the new one.
		// However if these two nodes are colocated or are very
		// close, we could get into an long or infinite recursion.
		// In this case, we simply increase the _weight
		// and ignore the second vertex in the quad.
		// We move that extra vertex aside by one pixel however
		// to avoid this issue next time.
		if (_right-_left<1 || (_position[0]==nx && _position[1]==ny)) 
		{
			v->position(Vector(nx+1,ny+1,0));
			_weight += 1.0;
			return;
		}
		force_add(_vertex);
		_vertex = NULL; // this is not a leaf anymore, so nullify _vertex
	}
	force_add(v);

	_position[0]=(_position[0]*_weight+nx)/(_weight+1.0);
	_position[1]=(_position[1]*_weight+ny)/(_weight+1.0);
	_weight+=1.0;
}

void QNode::area(float &left, float &top, float &right, float &bottom) 
{
	left = _left; 
	top = _top;
	right = _right;
	bottom = _bottom; 
}

void QNode::traverse(bool (*trav_func)(QNode*,void*), void *data)
{
	if (trav_func(this,data))
	{
		if (_tl) _tl->traverse(trav_func,data);
		if (_tr) _tr->traverse(trav_func,data);
		if (_bl) _bl->traverse(trav_func,data);
		if (_br) _br->traverse(trav_func,data);
	}
}


QNode::~QNode()
{
	if (_tl) delete _tl;
	if (_tr) delete _tr;
	if (_bl) delete _bl;
	if (_br) delete _br;
}
/*
void QNode::dump(const char *title, unsigned depth)
{
	static char indent[104];
	
	if (depth>49) 
	{
		printf("Error!\n");
	}

	indent[depth]=0;
	
	printf("%p %s%s[%u %g %g]-(%g,%g,%g,%g)\n",this,indent,title,_weight,_x,_y,_left,_top,_right,_bottom);
	indent[depth++]=' ';
	indent[depth++]=' ';
	if (_tl) _tl->dump("TL",depth);
	if (_tr) _tr->dump("TR",depth);
	if (_bl) _bl->dump("BL",depth);
	if (_br) _br->dump("BR",depth);
}

#include <stdlib.h>
int main()
{
	QNode* core = QNode::create(0,0,100.0,100.0);

	for (unsigned i=0;i<100;i++)
	{
		core->add(1.0*(rand()%100),1.0*(rand()%100));
	}

	core->dump("**");

	delete core;
}*/
